k-d tree implementation [closed]

Posted by user466441 on Programmers See other posts from Programmers or by user466441
Published on 2012-09-03T14:11:04Z Indexed on 2012/09/03 15:50 UTC
Read the original article Hit count: 245

Filed under:
|

when i run my code and debugged,i got this error

    -       this    0x00093584 {_Myproxy=0x00000000 _Mynextiter=0x00000000 }    std::_Iterator_base12 * const
    -       _Myproxy    0x00000000 {_Mycont=??? _Myfirstiter=??? }  std::_Container_proxy *
            _Mycont CXX0017: Error: symbol "" not found 
            _Myfirstiter    CXX0030: Error: expression cannot be evaluated  
    +       _Mynextiter 0x00000000 {_Myproxy=??? _Mynextiter=??? }  std::_Iterator_base12 *

but i dont know what does it means,code is this

    #include<iostream>
    #include<vector>
    #include<algorithm>

    using namespace std;
    struct point
    {
        float x,y;

        };
    vector<point>pointleft(4);
    vector<point>pointright(4);
    //we are going to implement two comparison function for x and y coordinates,we need it in calculation of median (we should sort vector
    //by x or y  according to depth informaton,is depth even or odd.
    bool sortby_X(point &a,point &b)
    {
        return a.x<b.x;
    }
    bool sortby_Y(point &a,point &b)
    {
        return a.y<b.y;
    }
    //so i am going to implement to median finding algorithm,one for finding median by x and another find median by y
    point medianx(vector<point>points)
    {
        point temp;
        sort(points.begin(),points.end(),sortby_X);
        temp=points[(points.size()/2)];
        return temp;
    }
    point mediany(vector<point>points)
    {
        point temp;
        sort(points.begin(),points.end(),sortby_Y);
        temp=points[(points.size()/2)];

        return temp;
    }
    //now construct  basic  tree structure 
    struct  Tree
    {
        float x,y;
        Tree(point a)
        {
            x=a.x;
            y=a.y;

        }
        Tree *left;
        Tree *right;
    };

     Tree * build_kd( Tree *root,vector<point>points,int depth)
     {
         point temp;
         if(points.size()==1)// that point is as a leaf
         {
              if(root==NULL)
             root=new Tree(points[0]);
              return root;

         }
         if(depth%2==0)
         {
             temp=medianx(points);
             root=new Tree(temp);
             for(int i=0;i<points.size();i++)
             {
                 if (points[i].x<temp.x)
                     pointleft[i]=points[i];
                 else
                     pointright[i]=points[i];
             }

         }
         else
         {
             temp=mediany(points);
             root=new Tree(temp);
             for(int i=0;i<points.size();i++)
             {
                 if(points[i].y<temp.y)
                     pointleft[i]=points[i];
                 else
                     pointright[i]=points[i];

             }


         }
          return build_kd(root->left,pointleft,depth+1);
          return build_kd(root->right,pointright,depth+1);
     }
       void print(Tree *root)
       {
           while(root!=NULL)
           {
               cout<<root->x<<"  " <<root->y;
               print(root->left);
               print(root->right);

           }

       }
    int main()
    {
        int depth=0;
        Tree *root=NULL;

        vector<point>points(4);
        float x,y;
        int n=4;
         for(int i=0;i<n;i++)
         {
             cin>>x>>y;
            points[i].x=x;
            points[i].y=y;

         }
         root=build_kd(root,points,depth);
         print(root);
            return 0;
    }

i am trying ti implement in c++ this pseudo code

    tuple function build_kd_tree(int depth, set points):
        if points contains only one point:
            return that point as a leaf.

        if depth is even:
            Calculate the median x-value.
            Create a set of points (pointsLeft) that have x-values less than
                the median.
            Create a set of points (pointsRight) that have x-values greater
                than or equal to the median.
        else:
            Calculate the median y-value.
            Create a set of points (pointsLeft) that have y-values less than
                the median.
            Create a set of points (pointsRight) that have y-values greater
                than or equal to the median.

        treeLeft = build_kd_tree(depth + 1, pointsLeft)
        treeRight = build_kd_tree(depth + 1, pointsRight)

        return(median, treeLeft, treeRight)

please help me what this error means?

© Programmers or respective owner

Related posts about c++

Related posts about trees